//题目:
// 给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。
 
// 示例 1：
// 输入：n = 2
// 输出：91
// 解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。 

// 示例 2：
// 输入：n = 0
// 输出：1
 
// 提示：
// 0 <= n <= 8
#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;
//代码
class Solution 
{
public:
    int countNumbersWithUniqueDigits(int n) 
    {
        //n就是数字x的位数
        if(n==0) return 1;
        //1.创建dp表————dp[i]表示：有i位的数中，各位都不同的数字的个数
        vector<int> dp(n+1);
        //2.初始化
        dp[1]=10;
        //3.填表————动态转移方程:dp[i]=dp[i-1]+(i位数中所有位的值都不相同的数字的个数)
        for(int i=2;i<=n;i++)
        {
            int sum=9;
            for(int j=2;j<=i;j++)
                sum*=(11-j);
            dp[i]=dp[i-1]+sum;
        }
        return dp[n];
    }
};